package com.dubious.interview.euler;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class Problem33 {

    /**
     * The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to
     * simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by 
     * cancelling the 9s.
     * 
     * We shall consider fractions like, 30/50 = 3/5, to be trivial examples.
     * 
     * There are exactly four non-trivial examples of this type of fraction, less than one in value, 
     * and containing two digits in the numerator and denominator.
     * 
     * If the product of these four fractions is given in its lowest common terms, find the value 
     * of the denominator.
     */
    public static int run()
    {
        
        // find the "interesting" "curious fractions".
        List<Integer> numerators = new ArrayList<Integer>(4);
        List<Integer> denominators = new ArrayList<Integer>(4);
        for(int i = 10; i <= 99; i++)
        {
            for(int j = i + 1; j <= 99; j++)
            {
                if(i % 10 == j / 10 && 1.0 * i / j == 1.0 * (i / 10) / (j % 10))
                {
                    numerators.add(i);
                    denominators.add(j);
                } else if(i / 10 == j % 10 && 1.0 * i / j == 1.0 * (i % 10) / (j / 10))
                {
                    numerators.add(i);
                    denominators.add(j);
                }
            }
        }
        
        // determine the numerator and denominator of the product of these curious fractions
        int numeratorProduct = 1;
        int denominatorProduct = 1;
        for(Integer numerator : numerators)
        {
            numeratorProduct *= numerator;
        }
        for(Integer denominator : denominators)
        {
            denominatorProduct *= denominator;
        }
        
        // to reduce the fraction we find the greatest common divisor and divide both numbers by this
        Set<Long> numeratorDivisors = Utilities.getDivisors((long)numeratorProduct);
        Set<Long> denominatorDivisors = Utilities.getDivisors((long)denominatorProduct);
        long greatestCommonDivisor = 1;
        for(Long numeratorDivisor : numeratorDivisors)
        {
            if(numeratorDivisor > greatestCommonDivisor && denominatorDivisors.contains(numeratorDivisor))
            {
                greatestCommonDivisor = numeratorDivisor;
            }
        }
        
        return denominatorProduct / (int)greatestCommonDivisor;
    }
}
